﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.Diagnostics;

namespace DoubleLinkedList
{
    public class Node<T>
    {
        public T value { get; set; }
        public Node<T> next { get; set; }
        public Node<T> prev { get; set; }
        public Node() {}
        public Node (T value)
        {
            this.value = value;
        }
    }

    public class DoubleLinked<T> : ICollection<T>
    {
        private Node<T> first;
        private Node<T> last;
        public DoubleLinked()
        {
            first = null;
            last = null;
        }

        public bool isEmpty()
        {
            return (first == null);
        }
        public T Front()
        {
            if(this.isEmpty())
            {
                throw new Exception("Empty List");
            }
            return first.value;
        }
        public T Last()
        {
            if (this.isEmpty())
            {
                throw new Exception("Empty List");
            }
            return last.value;
        }

        public void AddFirst(T item)
        {
            Node <T> n = new Node<T>(item);
            if(this.isEmpty())
            {
                this.first = n;
                this.last = n;
            }
            else
            {
                first.prev = n;
                n.next = first;
                first = n;
            }
        }
        public void AddLast(T item)
        {
            Node<T> n = new Node<T>(item);
            if(this.isEmpty())
            {
                this.first = n;
                this.last = n;
            }
            else
            {
                last.next = n;
                n.prev = last;
                last = n;
            }
        }
        public T Find(T item)
        {
            foreach(var node in this)
            {
                if(item.Equals(node))
                {
                    return node;
                }
            }
            throw new Exception("Item not in list");
        }
        public void RemoveFirst()
        {
            if (this.isEmpty())
            {
                throw new Exception("Empty List");
            }
            first = first.next;
        }
        public void RemoveLast()
        {
            if (this.isEmpty())
            {
                throw new Exception("Empty List");
            }
            last = last.prev;
        }


        #region ICollection
        public void Add(T item)
        {
            //AddFirst(item);
            throw new NotImplementedException();
        }
        public void CopyTo(T[] array, int arrayIndex)
        {
            throw new NotImplementedException();
        }
        public bool IsReadOnly
        {
            get { return false; }
        }
        public bool Remove(T item)
        {
            if(this.isEmpty())
            {
                return false;
            }
            if(item.Equals(first.value))
            {
                RemoveFirst();
                return true;
            }
            else if(item.Equals(last.value))
            {
                RemoveLast();
                return true;
            }
            Node<T> nprev = first;
            Node<T> n = first.next;
            while(n != null)
            {
                if(item.Equals(n.value))
                {
                    nprev.next = n.next;
                    return true;
                }
                nprev = n;
                n = n.next;
            }
            
            return false;
        }
        public int Count
        {
            get { throw new NotImplementedException(); }
        }
        public bool Contains(T item)
        {
            foreach (var value in this)
            {
                if(item.Equals(value))
                {
                    return true;
                }
            }
            return false;
        }
        public void Clear()
        {
            this.first = null;
            this.last = null;
        }
        public IEnumerator<T> GetEnumerator()
        {
            Node<T> n = first;

            while (n != null)
            {
                yield return n.value;
                n = n.next;
            }
        }
        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
        #endregion
    }
}
